import java.lang.reflect.Array;
import java.util.Arrays;

public class Test12_1 {
    /**
     *
     * @param matrix 输入的矩阵
     * @param row 行
     * @param col 列
     * @param str 要搜索的字符
     * @return
     */
    public static  boolean hasPath(char[] matrix,int row,int col,char[] str){
        if (matrix == null || matrix.length != row*col ||str == null || str.length == 0) return  false;

        boolean[] visited = new boolean[row*col];
        Arrays.fill(visited,false);

        //结果记录
        int[] pathLength = {0};
        //以每一个点为起点进行搜索
        for (int i = 0; i< row;i++){
            for (int j = 0; j<col;j++){
                if (hasPathCore(matrix,row,col,str,visited,i,j,pathLength)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     *
     * @param matrix 输入的矩阵
     * @param rows 行
     * @param cols 列
     * @param str 要寻找的字符
     * @param visited 是否遍历过
     * @param currow 当前处理的行号
     * @param curcol 当前处理的行号
     * @param pathLength 已处理的str中字符的个数
     * @return
     */
    public static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, boolean[] visited,
                                      int currow, int curcol, int[] pathLength){
        if (pathLength[0] == str.length) return true;
        boolean haspath = false;
        //当前行大于0且小于总行数，当前列大于0且小于总列数，当前字符 == 要处理的字符 没有遍历过当前字符
        if (currow >= 0 && currow<rows && curcol >=0 && curcol < cols && matrix[currow*cols+curcol]  == str[pathLength[0]] && !visited[currow*cols+curcol]){
            visited[currow * cols + curcol] = true;
            pathLength[0]++;

            //回溯
            haspath = hasPathCore(matrix,rows,cols,str,visited,currow,curcol+1,pathLength) ||
                    hasPathCore(matrix,rows,cols,str,visited,currow+1,curcol,pathLength) ||
                    hasPathCore(matrix,rows,cols,str,visited,currow,curcol-1,pathLength) ||
                    hasPathCore(matrix,rows,cols,str,visited,currow-1,curcol,pathLength);
            if (!haspath){
                pathLength[0] --;
                visited[currow*cols+curcol] = false;
            }
        }
        return haspath;
    }

    public static void main(String[] args) {
        //ABCE  //ABCCED
        //SFCS
        //ADEE
        System.out.println(hasPath("ABCESFCSADEE".toCharArray(), 3, 4,
                "ABCCED".toCharArray()) );// true
    }
}
